public class HuffmanTree<T> {
    private final  int maxSize = 100;
    public HuffmanNode<T>[] nodes; //哈夫曼树的各结点
    public int length; //有效结点个数

    public HuffmanTree()
    {
        nodes = new HuffmanNode[maxSize];
        length = 0;

    }
    /**
     * 从所有离散的结点中选择权重最小的结点并返回其位置编号
     * 如果该结点不存在，则返回-1
     */
    private int selectMini(){
        int t = -1;
        //寻找第一个离散的结点
        for (int i = 0; i < this.length; i++)
        {
            if (nodes[i].parent==0)
            {
                t = i;
                break;
            }
        }
        //寻找权重最小的离散结点
        for (int i = 0; i < this.length; i++)
        {
            if (nodes[i].parent==0 && nodes[t].weight > nodes[i].weight)
            {
                t = i;
            }
        }
        //将权重最小的离散结点的双亲设置为-1，表示已选中该结点，以避免选择权重次小的结点时重复选中该结点
        if (t!=-1) nodes[t].parent = -1;
        return t;
    }

    public void create()
    {
        int first = -1;
        int second = -1;
        do{
            first = selectMini(); //选取权重最小的结点
            second = selectMini(); //选取权重次小的结点
            if (second != -1)
            {
                double weight = nodes[first].weight + nodes[second].weight;
                //构造二叉树的根节点，其权重为左右孩子结点权重之和
                HuffmanNode<T>  node = new HuffmanNode<>(null,weight);
                node.lchild=first;
                node.rchild=second;
                nodes[length]=node;
                nodes[first].parent = length;
                nodes[second].parent=length;
                length++;
            }
        }
        while (second!=-1);
    }
}

